import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-26
 * Time:15:48
 */
class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(){

    }
    public TreeNode(int val) {
        this.val = val;
    }
}
class Solution {

    //先序遍历将树的值转化成字符串
    public String tree2str(TreeNode root) {
        String str=new String();
        //先序遍历
        if(root==null){
            return str;
        }
        str.
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
       if(root==null){
           return list;
       }
        while(root!=null||!stack.isEmpty()){
            if(root!=null){
                stack.push(root);
                list.add(root.val);
                root=root.left;
            }else{
                root=stack.pop().right;
            }
        }
        return list;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root==null){
            return list;
        }
        //进入循环
        while(root!=null||!stack.isEmpty()){
            //左子树的左边全部进去
            if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
                list.add(stack.peek().val);
                root=stack.pop().right;
            }
        }
        return list;
    }
//    public static List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> list=new ArrayList<>();
//        Stack<TreeNode> stack=new Stack<>();
//        TreeNode cur= new TreeNode();
//        if(root==null){
//            return list;
//        }
//        //进入循环
//        //问题存不上根节点的值
//        while(root!=null||!stack.isEmpty()){
//            if(cur==root){
//                list.add(stack.pop().val);
//            }
//            //左子树的左边全部进去
//            if(root!=null){
//                stack.push(root);
//                root=root.left;
//            }else{
//                root=stack.peek().right;
//                if(cur==root){
//                    list.add(stack.pop().val);
//                }
//                //如果右子树是空的
//                cur=root;
//            }
//        }
//        return list;
//    }
    //正确的后续非递归遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode prev=null;
        if(root==null){
            return list;
        }
        //进入循环
        while(root!=null||!stack.isEmpty()){
            //左子树的左边全部进去
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            TreeNode cur=stack.peek();
            if(cur.right==null||cur.right==prev){
                list.add(stack.pop().val);
                prev=cur;
            }
            else{
                root=stack.peek().right;
            }
        }
        return list;
    }
    //前中建立二叉树
    int cur=0;
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int begin,int end){
        //当前节点是不是还有其他的子树
        if(begin>end){
            return null;
        }
        TreeNode root=new TreeNode(preorder[cur]);
        int ret=find(inorder,begin,end,preorder[cur]);
        //在此子树区间内有没有这个值
        if(ret==-1){
            return null;
        }
        cur++;
        //找完了
        if(begin>=end){
            return root;
        }
        root.left=buildTreeChild(preorder,inorder,begin,ret-1);
        root.right=buildTreeChild(preorder,inorder,ret+1,end);
        return root;
    }
    public int find(int[]inorder,int begin,int end,int val){
        for (int i = begin; i <= end; i++) {
            if(inorder[i]==val){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root=new TreeNode(preorder[cur]);
        int ret=find(inorder,0,inorder.length-1,preorder[cur]);
        cur++;
        root.left=buildTreeChild(preorder,inorder,0,ret-1);
        root.right=buildTreeChild(preorder,inorder,ret+1,inorder.length-1);
        return root;
    }
}
public class Test {
    public static TreeNode create(){
        TreeNode node1=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        node1.right=node2;
        node2.left=node3;
        return node1;
    }
    public static void main(String[] args) {
        List<Integer> list =new ArrayList<>();
        TreeNode node =create();
        //list=Solution.postorderTraversal(node);
        //list.toString();
    }
}
